package LinkedList;

import java.util.Stack;
/**
 * 描述
 * 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
 * 给定两个这种链表，请生成代表两个整数相加值的结果链表。
 * 数据范围：0≤n,m≤1000000，链表任意值 0≤val≤9
 * 要求：空间复杂度 O(n)，时间复杂度 O(n)
 *
 * 例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
 *
 * */
class BM11 {
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        //申请两个栈空间和一个标记位，然后将两个栈中内容依次相加，将结果头插法加入新节点中
        //O(max(m,n))
        /**
         * 复杂度分析：
     *         时间复杂度：O(max(m,n))，由于只遍历了一次，只需要看两个链表更长的
     *         空间复杂度：O(m+n)，申请了两个栈来记录元素
         *
         * */
        if(head1==null){
            return head2;
        }
        if(head2==null){
            return head1;
        }
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        //将链表的值都放进去
        while(head1!=null){
            stack1.push(head1.val);
            head1 = head1.next;
        }
        while(head2!=null){
            stack2.push(head2.val);
            head2 = head2.next;
        }
        int flag = 0;  //标志位

        ListNode newNode = null;
        ListNode head = null; //新建链表的头
        while(!stack1.empty() || !stack2.empty() ){
            int num1 = stack1.empty() ? 0 : stack1.pop(); //为空就取0，不空就取栈顶
            int num2 = stack2.empty() ? 0 : stack2.pop(); //为空就取0，不空就取栈顶
            int sum = num1+num2+flag;
            flag = sum/10;  //更新标志位
            //将计算值放入节点
            newNode = new ListNode(sum % 10);
            //更新下一个节点的指向
            newNode.next = head;
            head = newNode;
        }
        if(flag==1){
            //将计算值放入节点
            newNode = new ListNode(1);
            //更新下一个节点的指向
            newNode.next = head;
            head = newNode;
        }
        return head;

    }
}
